package com.watson.onebox.algorithm.heap;

public class MaxHeap {
    private int n;       //堆的可容量大小
    private int count;   //索引
    private int[] data;  //创建堆时需要的额外空间，此处以int为例，也可以是其他类型

    public MaxHeap(int[] a, int n) {  //设堆根元素下标从1开始
        data = new int[n + 1];
        this.count = n;
        this.n = n;
        for (int i = 0; i < n; i++)
            data[i + 1] = a[i];
        for (int i = count / 2; i >= 1; i--)
            shiftDown(i);
        System.out.println(a);
    }

    public void put(int x) {   //插入一个堆元素
        if (count + 1 > n) System.exit(0); //数组越界则退出程序
        data[++count] = x;
        shiftUp(count);
    }

    //取出最大值
    public int removeMax() {
        if (count < 1) System.exit(0);  //数组越界则退出程序
        int x = data[1];
        swap(data, 1, count--);
        shiftDown(1);
        return x;
    }

    private void shiftUp(int k) {
        while (k > 1 && data[k / 2] < data[k]) {
            swap(data, k, k / 2);
            k /= 2;
        }
    }

    private void shiftDown(int k) {
        while (2 * k <= count) { //左孩子是否存在
            int i = 2 * k;
            if ((i + 1 <= count) && (data[i] < data[i + 1]))  //左右孩子
                i++;
            if (data[i] <= data[k]) break;
            swap(data, i, k);
            k = i;
        }
    }

    public int size() {  //堆元素个数
        return count;
    }

    public boolean isEmpty() {  //判空
        return count == 0;
    }

    private void swap(int[] src, int a, int b) {
        int tmp = src[a];
        src[a] = src[b];
        src[b] = tmp;
    }

    public static void heapSort2(int[] a) {  //heapify
        MaxHeap heap = new MaxHeap(a, a.length);
        for (int i = a.length - 1; i >= 0; i--)
            a[i] = heap.removeMax();
    }

    public static void main(String[] args) {
        int[] nums = {2, 42, 6, 201, 4, 7, 12, 43, 32, 876};

        MaxHeap maxHeap = new MaxHeap(nums, nums.length);
        heapSort2(nums);
        System.out.println(nums);

    }
}
